package cn.bellychang.leetcode.question108;

/**
 * Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
 * <p>
 * For this problem, a height-balanced binary tree is defined as a binary tree
 * in which the depth of the two subtrees of every node never differ by more than 1.
 *
 * @author ChangLiang
 * @date 2021/2/8
 */
public class Solution {

    public TreeNode sortedArrayToBST(int[] nums) {

        // 1. 大问题 分解为 小问题
        // 每次取数组最中间的节点为中节点 左侧为左子树的内容 右侧为右子树的内容

        // 2. 递推公式
        // tree = 左子树 连接上 右子树


        return insertBST(0, nums.length - 1, nums);
    }

    private TreeNode insertBST(int beginIndex, int endIndex, int[] nums) {
        // 3. 终止条件
        if (beginIndex > endIndex) {
            return null;
        }
        if (beginIndex == endIndex) {
            return new TreeNode(nums[beginIndex]);
        }
        int mid = ((endIndex - beginIndex) >> 1) + beginIndex;
        TreeNode curr = new TreeNode(nums[mid]);
        curr.left = insertBST(beginIndex, mid - 1, nums);
        curr.right = insertBST(mid + 1, endIndex, nums);
        return curr;
    }
}
